package com.github.hgkmail.hello.interview.mysql.design;

//自平衡的多叉查找树 —— B树
//与二叉查找树BST非常类似，中序遍历也是有序递增数列
//不同点1，有个参数"度"（degree）控制每个节点的关键字数量范围，太多就分裂，太少就合并
//不同点2，B树的插入是向上生长（关键字上浮），B树的删除是向下生长（关键字下沉），与BST相反，与直观感觉相背
//优点，由于每个节点可以存放多个关键字，树高增加慢，可以存放百万记录
public class BTree {
    class BTreeNode {
        int[] keys; //关键字，keys[i]左边孩子是children[i]，右边孩子是children[i+1]
        BTreeNode[] children; //孩子节点
        int keyNum; //关键字个数
        boolean leaf; //是否叶子节点
        int degree; //最小度，一个节点关键字个数: t-1 <= keyNum <= 2t-1
    }

    //todo 参考：什么是B树 https://zhuanlan.zhihu.com/p/146252512
}
